﻿using System;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Knapsack
{
    public class IterativeKnapsackSolver : IKnapsackSolver
    {
        private readonly Func<int,int,IMap<Tuple<int, int>, double>> _createMap;

        public IterativeKnapsackSolver(Func<int,int,IMap<Tuple<int,int>,double>> createMap = null)
        {
            _createMap = createMap ?? ((a,b) => AlgoritmiaFactory.Maps<Tuple<int, int>, double>.Default);
        }


        public double Profit(int W, IList<double> values, IList<int> weights)
        {
            var N = values.Count;
            var B = _createMap(N,W);
            for(int c = 0; c <= W; c++)
            {
                B[new Tuple<int, int>(0, c)] = 0;
            }
            for(int n = 1; n <= N; n++)
            {
                for(int c = 0; c < weights[n-1]; c++)
                {
                    B[new Tuple<int, int>(n, c)] = B[new Tuple<int, int>(n - 1, c)];
                }
                for(int c = weights[n-1]; c <= W; c++)
                {
                    B[new Tuple<int, int>(n, c)] = Math.Max(B[new Tuple<int, int>(n - 1, c)],
                                                            B[new Tuple<int, int>(n - 1, c - weights[n - 1])] +
                                                            values[n - 1]);
                }
            }
            return B[new Tuple<int, int>(N, W)];
        }
    }
}
